%% bare_conf.tex
%% V1.3
%% 2007/01/11
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.7 or later) with an IEEE conference paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/tex-archive/macros/latex/contrib/IEEEtran/
%% and
%% http://www.ieee.org/

%%*************************************************************************

\documentclass[conference]{IEEEtran}

% Add the compsoc option for Computer Society conferences.
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/tex-archive/macros/latex/contrib/oberdiek/
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 4.0 (2003-05-27) and later if using hyperref.sty. cite.sty does
% not currently provide for hyperlinked citations.
% The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/cite/
% The documentation is contained in the cite.sty file itself.




% *** MATH PACKAGES ***
%
%\usepackage[cmex10]{amsmath}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics. If using
% it, be sure to load this package with the cmex10 option to ensure that
% only type 1 fonts will utilized at all point sizes. Without this option,
% it is possible that some math symbols, particularly those within
% footnotes, will be rendered in bitmap form which will result in a
% document that can not be IEEE Xplore compliant!
%
% Also, note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/amslatex/math/


\usepackage[pdftex]{graphicx}


% *** SPECIALIZED LIST PACKAGES ***
%
\usepackage{algorithm}
\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithms/
% There is also a support site at:
% http://algorithms.berlios.de/index.html
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/tex-archive/macros/latex/contrib/algorithmicx/




% *** ALIGNMENT PACKAGES ***
%
%\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/required/tools/


%\usepackage{mdwmath}
%\usepackage{mdwtab}
% Also highly recommended is Mark Wooding's extremely powerful MDW tools,
% especially mdwmath.sty and mdwtab.sty which are used to format equations
% and tables, respectively. The MDWtools set is already installed on most
% LaTeX systems. The lastest version and documentation is available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/mdwtools/


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.


%\usepackage{eqparbox}
% Also of notable interest is Scott Pakin's eqparbox package for creating
% (automatically sized) equal width boxes - aka "natural width parboxes".
% Available at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/eqparbox/





% *** SUBFIGURE PACKAGES ***
%\usepackage[tight,footnotesize]{subfigure}
% subfigure.sty was written by Steven Douglas Cochran. This package makes it
% easy to put subfigures in your figures. e.g., "Figure 1a and 1b". For IEEE
% work, it is a good idea to load it with the tight package option to reduce
% the amount of white space around the subfigures. subfigure.sty is already
% installed on most LaTeX systems. The latest version and documentation can
% be obtained at:
% http://www.ctan.org/tex-archive/obsolete/macros/latex/contrib/subfigure/
% subfigure.sty has been superceeded by subfig.sty.



%\usepackage[caption=false]{caption}
%\usepackage[font=footnotesize]{subfig}
% subfig.sty, also written by Steven Douglas Cochran, is the modern
% replacement for subfigure.sty. However, subfig.sty requires and
% automatically loads Axel Sommerfeldt's caption.sty which will override
% IEEEtran.cls handling of captions and this will result in nonIEEE style
% figure/table captions. To prevent this problem, be sure and preload
% caption.sty with its "caption=false" package option. This is will preserve
% IEEEtran.cls handing of captions. Version 1.3 (2005/06/28) and later
% (recommended due to many improvements over 1.2) of subfig.sty supports
% the caption=false option directly:
%\usepackage[caption=false,font=footnotesize]{subfig}
%
% The latest version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/subfig/
% The latest version and documentation of caption.sty can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/caption/




% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure. The latest version and documentation can be found at:
% http://www.ctan.org/tex-archive/macros/latex/base/



%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/sttools/
% Documentation is contained in the stfloats.sty comments as well as in the
% presfull.pdf file. Do not use the stfloats baselinefloat ability as IEEE
% does not allow \baselineskip to stretch. Authors submitting work to the
% IEEE should note that IEEE rarely uses double column equations and
% that authors should try to avoid such use. Do not be tempted to use the
% cuted.sty or midfloat.sty packages (also by Sigitas Tolusis) as IEEE does
% not format its papers in such ways.





% *** PDF, URL AND HYPERLINK PACKAGES ***
%
%\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version can be obtained at:
% http://www.ctan.org/tex-archive/macros/latex/contrib/misc/
% Read the url.sty source comments for usage information. Basically,
% \url{my_url_here}.





% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%
% paper title
% can use linebreaks \\ within to get better formatting as desired
\title{Matrix Product Verification Simulator}


% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
\author{\IEEEauthorblockN{Yixing Geng}
\IEEEauthorblockA{
Email: yixingengcn@tamu.edu}
\and
\IEEEauthorblockN{Chelsea Hall}
\IEEEauthorblockA{
Email: hallcr@cse.tamu.edu}
\and
\IEEEauthorblockN{Andrew Koons}
\IEEEauthorblockA{
Email: andrewkoons@gmail.com }}


% make the title area
\maketitle


\begin{abstract}
The theory of quantum computation, and the subsequent development of quantum algorithms, has had some important 
implications for the classical algorithms used today. Specifically, the research into quantum algorithms has benefitted 
the classical counterparts and allowed for increased efficiency. This paper seeks to explore the developments of quantum 
algorithms for verification of matrix products. The goal of this project is to implement a classical version of a 
quantum matrix product verification algorithm and perform analysis of the classical implementation. The runtime of the classical 
algorithm was determined to be o($nlog(n^{\frac{2}{3}})$),
which was even slower than expected. Therefore steps should be taken to increase the efficiency of the algorithm for it to be viable.
\end{abstract}
% IEEEtran.cls defaults to using nonbold math in the Abstract.
% This preserves the distinction between vectors and scalars. However,
% if the conference you are submitting to favors bold math in the abstract,
% then you can use LaTeX's standard command \boldmath at the very start
% of the abstract to achieve this. Many IEEE journals/conferences frown on
% math in the abstract anyway.

% no keywords




% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle

\section{Introduction}
Quantum verification of matrix products is an area of research with the goal of verifying $AB=C$, when given three 
$n$ x $n$ matrices $A$, $B$, and $C$. The focus of this project is to implement a classical algorithm based on the 
quantum counterpart as outlined by Buhrman and Spalek\cite{QuantumVer:buhrman}. The basis of the quantum algorithm, 
and the development of the classical variant, will be presented in subsequent sections. Another focus of this project 
is to determine the comparable efficiency between these two algorithms. However, it must be noted that without a 
quantum computer, calculating the efficiency of the quantum algorithm is not possible. Even simulating the algorithm 
on a classical computer would not produce an accurate representation of the efficiency. Therefore, for the purpose of 
the analysis, the performance of the classical algorithm will be compared to the data from Buhrman and Spalek. In 
short, the projected run time of the classical algorithm will be compared against the theorized run time of the quantum 
algorithm.
\\
\section{Background Information}
\subsection{History}
The best known classical algorithm for the verification of matrix products was introduced by Rusins Freivald. The simple way of solving 
the matrix product verification problem would be to multiply $AB$ and then compare the result to $C$. This, however,
has a running time of O($n^{2.37}$), meaning the algorithm is very inefficient. Freivald's algorithm calculates the value of $A(Bx)$ and 
compares it to $Cx$ where $x$ is a collection of randomly choosen vectors. This algorithm decreases the running time for classical verification
to O($n^2$) \cite{Classical:Freivald}. The first look into using quantum algorithms to solve the matrix product verification problem was
developed by Ambainis, Buhrman, Hoyer, Karpinski, and Kurur.\footnote{Ambainis, et al. "Quantum matrix verification." Unpublished manuscript (2002).} 
Their algorithm used an implementation of Grover's search algorithm to perform their verification. This algorithm was an improvement over the 
classical algorithm to O($n^{\frac{7}{4}}$) \cite{QuantumVer:buhrman}.

\subsection{Grover's Search Algorithm}
Grover's search algorithm was developed in 1996 by Lov Grover\footnote{Grover, Lov K. "A fast quantum mechanical algorithm for database search." 
Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM, 1996.}. This quantum algorithm was developed to search an unsorted database in
O($\sqrt{n}$) time, where $n$ is the number of entries in the database. This is a marked improvement on the best known 
classical search algorithm which performs in O($n$) time. The quantum search algorithms were designed to find an element from a set of entries where the 
element is pursuant to specific properities and the nature of the order of the entries is unknown.\cite{Grover:Lavor}. Grover's search algorithm was the 
basis of the Ambainis, et al. algorithm for verification of matrix products. The
algorithm created by Ambainis, and later improved by Szegedy, used a property of the Grover's search algorithm that allows the algorithm to
determine the $x$ values that are associated with a particular $y$. In other words, given the function $y = f(x)$, the algorithm will calculate $x$ 
when given $y$. In the algorithm created by Ambainis, a random vector $x$ of length $\sqrt{n}$ is multiplied on both sides of the equation $AB=C$. 
Then the equation $y=Bx$ and $z=Cx$ will be calculated, and the matrix-vector product $Ay=z$ will be verfied by Grover's search\cite{QuantumVer:buhrman}.

\subsection{Quantum Walk}
The quantum algorithm we will be using involves a more general implementation of the Grover's search algorithm. This more genaral version
is called a quantum walk on a markov chain. A markov chain is considered to be a sequence of states such that each state is independent of the chain. The 
next state is only dependent on the current state and not any of the preceding states \cite{book:Nielsen}. In the 2004 paper by Szegedy on the quantum speedup 
of markov chain based algorithms, he generalized the quantum walk algorithm to find a marked vertex in an undirected graph. A quantum walk 
consists of two unitary transformations, a coin flip  operation and a shift operation. The coin flip is independent of the current state and will determine the 
direction of the shift. The shift operator shifts the state to a neighboring state in the direction of the coin flip. The typical operator for the coin flip operator
is a Hadamard, resulting in an unbiased coin flip. The use of a quantum walk in the quantum matrix product verification algorithm is intended 
to identify the values that result in $AB \neq C$ in square root of the classical running time \cite{Markov:Szegedy}.  

\section{Quantum Algorithm}
The quantum algorithm that our classical algorithm was
based on was defined by Buhrman and Spalek [1]. This 
algorithm uses the quantum random walk developed by 
Szegedy as its basis. The algorithm's function \emph{VerifyOnce}
will estimate the scalar product of the superposition as 
computed by the quantum walk and the uniform 
superposition. A check is done during each 
loop of the quantum walk by \emph{VerifyOnce} to verify if 
$a_R \cdot b_S \neq c_{R,S}$. The values $a_R$, $b_S$, and $c_{R,S}$ 
are defined as $a_R=p|^R\cdot A|_R$, $b_S=B|^S\cdot q|_S$, and $c_{R,S}=p|^R\cdot C|^R_S\cdot q|_S$, where p and q are random vectors.
This inequality can only be true if $A|_R \cdot B|^S \neq C|_R^S$. If this inequality
proves true, then the result state, $|z\rangle$, will go through a phase shift and when measured will result in a value
of 1. Otherwise, the result state is left unmodified. The expected run time of this algorithm as calculated by Buhrman and Spalek is
O($n^{\frac{5}{4}}$). 

\subsection{Pseudo-Code}
The pseudo-code for this algorithm is shown in the figure to the right, Algorithm 1.
\newcommand{\IND}[1][1]{\hspace{#1\algorithmicindent}}
\begin{algorithm}[h!]
\caption{Quantum Verification of Matrix Products}\label{alg:factorial}
\begin{algorithmic}
\REQUIRE $A$, $B$, $C$ such that $A$, $B$, and $C$ are matricies of size $n$ x $n$.
\medskip
\STATE \textbf{ProductVerification}(A,B,C,n)
  \STATE Take random $\lambda$, such that $ 1 < \lambda < \frac{8}{7}$
  \FOR{$i = 0,1,...,log_\lambda (n^{\frac{2}{3}}) + 9$}
    \STATE Set Result as Call \textbf{VerifyOnce}($2\lambda^i$)
    \IF{Result is 1} \RETURN 1 \ENDIF
  \ENDFOR
  \RETURN 0
\STATE
\STATE \textbf{VerifyOnce}(number of rows k)
\STATE Set number of iterations $l$ at random from ${1,2,...,k}$ 
\STATE Pick a random row vector $p$ 
\STATE Pick a random column vector $q$
\STATE \emph{Initialization}: 
\STATE Put the quantum registers into superposition 
  $\sum_{^{R\subseteq [n]}_{|R|=k}}\sum_{^{S\subseteq [n]}_{|S|=k}}|R\rangle |S\rangle$. 
\STATE Compute $a_R=p|^R\cdot A|_R$, $b_S=B|^S\cdot q|_S$, and
    $c_{R,S}=p|^R\cdot C|^R_S\cdot q|_S$
\STATE Set $|z\rangle = |0\rangle$ and apply a Hadamard
    transform to $|z\rangle$
\STATE \emph{Quantum Walk}: 
\FOR{$l$ iterations}
\STATE\emph{Phase flip}: 
\IF{$a_R\cdot b_S \neq c_{R,S}$} \STATE Multiply the quantum phase by -1 \ENDIF
\STATE\emph{Diffusion}:
\STATE Perform one step of a quantum walk on ($S,R$)
\ENDFOR
\STATE Apply the Hadamard transform on $|z\rangle$
\STATE Measure $|z\rangle$ 
\RETURN $|z\rangle$
\end{algorithmic}
\end{algorithm}

\section{Implementation}
As previously stated, the goal of this project is to create a classical algorithm for matrix multiplication 
verification in lieu of a quantum one, due to the lack of a quantum computer. However this algorithm must maintain 
the fast running time and high probablity of correct output that one would associate with a quancum algorithm. 
These were the main factors considered during the implementation process.

\subsection{Algorithm}
\subsubsection{Initialization}
The algorithm begins by choosing a number $1 < \lambda < \frac{8}{7}$, which is used to determine the number
of times that $VerifyOnce$ is run, $i$, by the formula $i=\log_\lambda(n^{\frac{2}{3}})+9 $. The loop calls 
$VerifyOnce$.
The function $VerifyOnce$ essentially picks a random vector from each matrix, and condenses them into the values 
that the quantum walk, the next step, needs.\\
In the simulator we developed, we manually set the cardinality $\vert n \vert$ of the vectors sets $R$ and $S$ in matricies $A$ and $B$ to be three. It must be noted that if
a random number was used then the calculation time will increase drastically. Then we randomly pick three rows of $A$ as $R$, and three columns of $B$ as $S$. Then we will 
have:$\textbf{a}_{R} = \textbf{p}\vert^{R}\cdot A\vert_{R}$ which is explicitly:
\[
\underbrace{(\ldots p_{R_1} \ldots p_{R_2} \ldots p_{R_3} \ldots)}_{\textbf{p}\vert^{R}}
\overbrace{\left(
\begin{array}{ccc}
\vdots & \vdots & \vdots \\
A_{R_{1} 1} & A_{R_{1} 2} & \ldots A_{R_{1} n}\\
\vdots & \vdots & \vdots \\
A_{R_{2} 1} & A_{R_{2} 2} & \ldots A_{R_{2} n}\\
\vdots & \vdots & \vdots \\
A_{R_{3} 1} & A_{R_{3} 2} & \ldots A_{R_{3} n}\\
\vdots & \vdots & \vdots \\
\end{array}
\right)}^{A\vert_{R}}
\]
In the same way we have the $\textbf{b}_{S} = B\vert^{S}\cdot \textbf{q}\vert_{S}$ which is explicitly:
\[
\overbrace{\left(
\begin{array}{ccc}
\cdots B_{1 S_{1}} \cdots B_{1 S_{2}} \cdots B_{1 S_{3}} \cdots \\
\cdots B_{2 S_{1}} \cdots B_{2 S_{2}} \cdots B_{3 S_{3}} \cdots \\
\vdots  \\
\cdots B_{n S_{1}} \cdots B_{n S_{2}} \cdots B_{n S_{3}} \cdots
\end{array}
\right)}^{B\vert^{S}}
\underbrace{
\left(
\begin{array}{ccc}
\vdots\\
q_{S_1}\\
\vdots\\
q_{S_2}\\
\vdots\\
q_{S_3}\\
\vdots\\
\end{array}
\right)
}_{\textbf{q}\vert_{S}}
\]
and finally $c_{R,S} = \textbf{p}\vert^{R}\cdot C\vert_{R}^{S} \cdot \textbf{q}\vert_{S}$ which is explicitly:
\[
\textbf{p}\vert^{R}
\overbrace{\left(
\begin{array}{ccc}
\cdots C_{1 S_{1}} \cdots C_{1 S_{2}} \cdots C_{1 S_{3}} \cdots \\
\vdots\\
C_{R_{1} 1}\cdots C_{R_{1} S_{1}} \cdots C_{R_{1} S_{2}} \cdots C_{R_{1} S_{3}} \cdots C_{R_{1} n}\\
\vdots  \\
C_{R_{2} 1}\cdots C_{R_{2} S_{1}} \cdots C_{R_{2} S_{2}} \cdots C_{R_{2} S_{3}} \cdots C_{R_{2} n}\\
\vdots  \\
C_{R_{3} 1}\cdots C_{R_{3} S_{1}} \cdots C_{R_{3} S_{2}} \cdots C_{R_{3} S_{3}} \cdots C_{R_{3} n}\\
\vdots  \\
\cdots C_{n S_{1}} \cdots C_{n S_{2}} \cdots C_{n S_{3}} \cdots \\
\end{array}
\right)}^{C\vert^{S}_{R}}
\textbf{q}\vert_{S}
\]
After calculating all the vectors and scalar, we join them together with the vector $\vert + \rangle$ and generate the initialized entanglement state:
\[
c_{R,S}\vert + \rangle \otimes \vert \textbf{a}_{R} \rangle \otimes \vert \textbf{b}_{S} \rangle 
\]
\subsubsection{Quantum Walk}
The quantum walk consists of a phase flip and diffusion. The phase flip will only occur if $a_R \cdot b_S \neq c_{R,S}$ where $a_R,b_S,$ and $c_{R,S}$ 
are the values found in the initialization. After the phase flip, the diffusion section finds
another set of vector values $a_R,b_S,$ and $c_{R,S}$. This quantum walk is performed $l$ times, where
$l$ is a random number from ${1,2,...,k}$ and $k$ is the number of rows in the original matricies. The quantum walk 
will verify whether or not the matrix multiplication is accurate. The walk will only make changes to the resulting 
vector if $AB \neq C$. 
\subsubsection{Results}
At the end of the quantum walk, a single qubit is returned, to which a hadamard gate is applied before measuring.
The resulting qubit can obviously have a value of either $0$ or $1$. If the former case is observed then there is a 
high probability that $AB \neq C$. Conversely, if the qubit is determined to be $0$ then the loop is run again. If the 
loop ends and the qubit was not found to be equal to $1$, then there is a high probability that $AB = C$.

\subsection{Pseudo-code}
\begin{algorithm}
\caption{Classical Verification of Matrix Products}\label{alg:factorial}
\begin{algorithmic}
\REQUIRE $A$, $B$, $C$ such that $A$, $B$, and $C$ are matricies of size $n$ x $n$.
\medskip
\STATE \textbf{ProductVerification}(A,B,C,n)
  \STATE Take random $\lambda$, such that $ 1 < \lambda < \frac{8}{7}$
  \FOR{$i = 0,1,...,(log_\lambda (n^{\frac{2}{3}}) + 9)16$}
    \STATE Set Result as Call \textbf{VerifyOnce}()
    \IF{Result is 1} \RETURN 1 \ENDIF
  \ENDFOR
  \RETURN 0
\STATE
\STATE \textbf{VerifyOnce}()
\STATE Set number of iterations $l$ at random from ${1,2,...,k}$ 
\STATE Pick a random row vector $p$ 
\STATE Pick a random column vector $q$
\STATE Pick a subset R of rows of A
\STATE Pick a subset S of columns of B
\FOR{$l$ iterations} 
\IF{$a_R\cdot b_S \neq c_{R,S}$} \STATE Apply PauliZ to $|z\rangle$ 
\ELSE \STATE Swap our $p$ and $q$ and reset R and S \ENDIF
\ENDFOR
\STATE Apply the Hadamard transform on $|z\rangle$
\STATE Measure $|z\rangle$ 
\RETURN $|z\rangle$
\end{algorithmic}
\end{algorithm}

\subsection{Limitations}
Obviously, a classical implementation of a quantum simulator can only hope to approximate, as 
close as possible, the run time of a true quantum computer. This could have a massive effect 
on our results. Grover's search algorithm, implemented on a classical computer, runs in
best case $O(n)$ time, where in a quantum implementation, it ideally runs in $O(\sqrt{n})$ time. 
Since this algorithm is based loosely on Grover's search, it is easy to suppose that our algorithm, 
implemented classically, will not run in the ideal quantum time.

Additionally, the algorithm works only for square matrices, and does not address the possibility
of multiplication of other matrices. Future work could be done to expand this algorithm to operate
effeciently on matricies of any compatable size. 
\\
\section{Analysis}
We disected the algorithm and determined our run time will most likely run
with expected time O($nlog(n^{\frac{2}{3}})$), which is a worse time than the quantum 
algorithm's proposed O($n^{\frac{5}{4}})$). This value was calculated by taking the $log(n)$ time
from the main \emph{for} loop, which executes the function \emph{VerifyOnce} $log(n^{\frac{2}{3}})$ times.
Inside of \emph{VerifyOnce}, we have a constant number of \emph{for} loops, which loop at most
$n$ times. It should be noted, however, that in addition to the slower 
run time, our algorithm has massive overhead. There are a large number of functions
inside of each \emph{for} loop, and a large number of \emph{for} loops that must be run. The
number of loops does not contribute to the O($nlog(n^{\frac{2}{3}})$) run time because they will always
run in constant time. They do, however, causes our algorithm to run noticeably slower than other implementations
would. The graph below showcases the differences in theoretical runtime between the quantum algorithm and the classical algorithm. 
\begin{center}
 \includegraphics[scale=.6,keepaspectratio=true]{./Graph.png}
 % Graph.png: 421x227 pixel, 72dpi, 14.85x8.01 cm, bb=0 0 421 227
\end{center}
As seen above, there is a distinct difference between the two runtimes. Whereas it was not expected for them to be equal, 
this discrepancy is potentially prohibitive. Therefore, in order for this algorithm to be practical, further refinement is needed. 
The run time of the classical algorithm will not meet the proposed O($n^{\frac{5}{4}}$), but it can be improved from O($nlog(n^{\frac{2}{3}})$). Additionally, 
the overhead can be reduced to improve efficiency. Future changes and improvements to this algorithm are discussed in a subsequent section.
\\
\section{Conclusion}
The goal of this project was to take the quantum algorithm for matrix multiplication verification and develop a classical 
implementation of it. Then, the theoretical runtimes of both algorithms was to be compared and analyzed. In that sense, the project was 
successful. The quantum algorithm was used to make a classical variant, and its runtime was determined to be O($nlog(n^{\frac{2}{3}})$). However, this runtime was a 
little slower than expected and signifies that there is still room for improvement. The potential areas for further work include trimming some of the 
overhead in the algorithm, allowing for non-square matrices, and including other matrix operations like addition or subtraction.
\\
\section{Future Work}
There may be even more refinement that can be done on this algorithm, though perhaps 
at an even greater loss of precision, for which the balance between the two can be a 
delicate thing. Firstly, it should be recognized that improved running time is a constant 
goal of research in this area. This is the case not only in matrix product verification, but in 
matrix operations in general. Especially in the field of quantum computing, matrix operations are 
fundamental, and any speedup possible could mean faster algorithms in general for the field. 

This algorithm only addresses the narrow case of multiplying $n$ x $n$ matrices, but similar algorithms may
potentially be derived from the proposed algorithm for other matrix operations, such as addition, subtraction,
transposition, inversion, Gauss-Jordan elimination, and finding the determinant. In addition, since this 
algorithm works strictly for matrices of size $n$ x $n$, it is currently unusable for the multiplication 
of matrices of different sizes, where the three input matrices would be of size $A = mn$, $B = np$, 
$C = mp$, for $AB = C$. There may very well be a way to expand this algorithm to include product 
verification for all valid matrix multiplication expressions. 

Additionally, there is no difinative proof yet that this is the fastest algorithm for this problem. A lower bound running 
time for algorithms of this type has yet to be verified, so a faster, or equally 
fast and more accurate algorithm for verification of matrix products may still exist. 

An attempt was made, in this project, to implement the 
quantum algorithm in a classical manner, though it is most likely far from the most optimal classical implementation. It 
can be expected that a strict implementation of the algorithm, rather than feeding the algorithm through a full quantum simulator, 
would be one of the fastest ways to translate this quantum algorithm into a classical algorithm.
\\

\begin{thebibliography}{1}
\bibitem{QuantumVer:buhrman}
H.~Buhrman and R.~$\breve{S}$palek, "Quantum verification of matrix products." Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. ACM, 2006.
\bibitem{Classical:Freivald}
R. ~Freivalds. Fast Probabilistic algorithms. In \emph{Proc. of 8th Symp. on Math. Foundations of Computer Science}, pages 57-69. Springer Verlag, 1979. LNCS 74.
\bibitem{RandomIntro:Kempe}
J.~Kempe, "Quantum random walks: an introductory overview." Contemporary Physics 44.4 (2003): 307-327.
\bibitem{Grover:Lavor}
C.~Lavor, L. R. U.~Manssur, and R.~Portugal. "Grover's algorithm: quantum database search." arXiv preprint quant-ph/0301079 (2003).
\bibitem{book:Nielsen}
A.~Nielsen and I.~Chuang. \emph{Quantum computation and quantum information.} Cambridge university press, 2010.
\bibitem{Markov:Szegedy}
M.~Szegedy, "Quantum speed-up of Markov chain based algorithms." Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on. IEEE, 2004.
\end{thebibliography}

\end{document}